﻿#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
public:
    // 56. 合并区间
    vector<vector<int>> merge(vector<vector<int>>& intervals)
    {
        int n = intervals.size();
        vector<vector<int>> ret;
        sort(intervals.begin(), intervals.end());
        int left = intervals[0][0], right = intervals[0][1];
        for (int i = 1; i < n; ++i)
        {
            int a = intervals[i][0], b = intervals[i][1];
            if (a <= right)
            {
                right = max(right, b);
            }
            else
            {
                ret.push_back({ left,right });
                left = a;
                right = b;
            }
        }
        ret.push_back({ left,right });
        return ret;
    }

    // 435. 无重叠区间
    int eraseOverlapIntervals(vector<vector<int>>& intervals)
    {
        sort(intervals.begin(), intervals.end());
        int n = intervals.size();
        int ret = 0;
        int left = intervals[0][0], right = intervals[0][1];
        for (int i = 1; i < n; ++i)
        {
            int a = intervals[i][0], b = intervals[i][1];
            if (a < right)
            {
                right = min(right, b);
                ret++;
            }
            else
            {
                right = b;
            }
        }
        return ret;
    }
};

int main()
{
    /*vector<vector<int>> v{ {1,3} ,{2,6},{8,10},{15,18} };
    Solution().merge(v);*/

    vector<vector<int>> v{ {1,2},{2,3},{3,4},{1,3} };
    cout << Solution().eraseOverlapIntervals(v) << endl;

    return 0;
}